package com.gao.r_hash.a;

import java.util.*;

/**
 * @author gao
 * @time 2022/04/29 21:17:27
 */
public class SlowHashSet<E> implements Set<E> {
    private LinkedList<E>[] arr = new LinkedList[1024];

    @Override
    public int size() {
        int totalSize = 0;
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == null) {
                continue;
            }
            totalSize += arr[j].size();
        }
        return totalSize;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public boolean contains(Object o) {
        // 散列，找桶位
        int hc = o.hashCode();
        int i = hc & (arr.length - 1);
        if (arr[i] == null) {
            return false;
        }
        for (int j = 0; j < arr[i].size(); j++) {
            if (arr[i].equals(o)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Object[] toArray() {
        Object[] objs = new Object[size()];
        int index = 0;
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == null) {
                continue;
            }
            for (int k = 0; k < arr[j].size(); k++) {
                objs[index++] = arr[j].get(k);
            }
        }
        return objs;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        Object[] objs = new Object[size()];
        int index = 0;
        for (int j = 0; j < arr.length; j++) {
            if (arr[j] == null) {
                continue;
            }
            for (int k = 0; k < arr[j].size(); k++) {
                objs[index++] = arr[j].get(k);
            }
        }
        return (T[]) objs;
    }

    @Override
    public boolean add(E e) {
        // 散列，找桶位
        int hc = e.hashCode();
        int i = hc & (arr.length - 1);

        // 如果桶位为空，则实例化桶位，并将新元素直接加入该桶位
        if (arr[i] == null) {
            arr[i] = new LinkedList<>();
            arr[i].add(e);
            return true;
        }
        /*
            如果桶位不为空，则判断该桶位中是否包含新元素，
            如果不包含则将新元素加入桶位。注意判断桶位是否
            包含新元素时，回调了新元素的equals方法
         */
        for (int j = 0; j < arr[i].size(); j++) {
            E elt = arr[i].get(j);
            if (e.equals(elt)) {
                return false;
            }
        }
        arr[i].add(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        int hc = o.hashCode();
        int i = hc & (arr.length - 1);
        if (arr[i] == null) {
            return false;
        }
        Object target = null;
        for (int j = 0; j < arr[i].size(); j++) {
            E elt = arr[i].get(j);
            if (o.equals(elt)) {
                target = elt;
            }
        }
        return arr[i].remove(target);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        boolean bb = false;
        for (E e : c) {
            bb |= add(e);
        }
        return bb;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean bb = false;
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            E e = it.next();
            if (!c.contains(e)) {
                remove(e);
                bb = true;

            }
        }
        return bb;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        boolean bb = false;
        for (Object o : c) {
            bb |= remove(o);
        }
        return bb;
    }

    @Override
    public Iterator<E> iterator() {
        return new SlowHashSetIterator<>();
    }

    @Override
    public void clear() {
        for (int i = 0; i < arr.length; i++) {
            arr[i].clear();
        }
    }

    /*
        使用内部类的优势
        1. 内部类自动关联外部类的对象
        2. 可以实例化多个内部类实例，以不同进度迭代同一个外部类SlowHashSet的对象
           如果直接让外部类SlowHashSet实现Iterator接口也不是不行，只不过不能以
           多个不同的进度来迭代SlowHashSet的对象了。
        3. 内部类看起来可以对外部类进行适配，优点适配器模式的味道，

        补充：
            以下代码也是迭代器设计模式和工厂方法设计模式的应用。
     */
    class SlowHashSetIterator<E> implements Iterator<E> {
        // i用于遍历整个数组，也就是遍历arr
        private int i = 0;
        // j用于遍历某个桶位，也就是遍历arr[i]
        private int j = 0;

        @Override
        public boolean hasNext() {

            while (i < arr.length) {
                while (i < arr.length && arr[i] == null) {
                    // 如果当前桶位是null，则迭代到下一个桶位
                    i++;
                }
                // 流程能走到这里，要么是数组遍历完了，要么是找到一个不为null的桶位
                // 以下判断就是确定是否是数组遍历完了，如果是，直接返回false，表示
                // 没有下一个元素了。
                if (i == arr.length) {
                    return false;
                }
                // 流程走到这里，说明找到一个不为空的桶位，j如果小于桶位的size，
                // 表示该桶位还有没有迭代到的值，就会返回true，表示整个SlowHashSet
                // 还有下一个值
                if (j < arr[i].size()) {
                    return true;
                }
                // 流程走到这里，说明迭代完一个桶位的所有元素了，该切换到下一个桶位了，
                // 同时将j的值归0，以便使用j继续迭代下一个不为null的桶位
                i++;
                j = 0;
            }

            // 流程走到这里，说明上面的大while循环的循环条件不成立了，说明整个数组迭代完毕
            // 所以返回false，表示没有下一个元素了。
            return false;
        }

        @Override
        public E next() {
            return (E) arr[i].get(j++);
        }
    }

}
